#define _CRT_SECURE_NO_WARNINGS
struct ListNode* findMid(struct ListNode* head)
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
struct ListNode* reverse(struct ListNode* head)
{
    struct ListNode* next1 = NULL;
    struct ListNode* prev = head;
    struct ListNode* tmp = head;
    while (prev)
    {
        if (prev)
            tmp = prev->next;
        prev->next = next1;
        next1 = prev;
        prev = tmp;
    }
    return next1;
}
bool isPalindrome(struct ListNode* head) {
    struct ListNode* mid = findMid(head);
    struct ListNode* cur1 = reverse(mid);
    struct ListNode* cur2 = head;
    while (cur2 && cur1)
    {
        if (cur1->val != cur2->val)
        {
            reverse(head);
            return false;
        }
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    reverse(head);
    return true;
}